package com.mxw.算法之美.a4队列;

/**
 * @author Administrator
 * @create 2024/7/16 17:23
 */
public class S01Queue {

    /**
     先进先出

     */

    /**
     * 顺序队列
     */
    public class ArrayQueue {
        private String[] items;
        private int n;

        // 队头下标
        private int head;

        // 队尾下标
        private int tail;

        // 初始化
        public ArrayQueue(int n) {
            this.items = new String[n];
            this.n = n;
            this.head = 0;
            this.tail = 0;
        }

        // 入队
        public boolean enqueue(String item) {
            // 如果tail == n 表示队列已经满了
            if (tail == n) {
                return false;
            }
            // 数据搬移：满了就把head-tail移动到0-tail
            for (int i = this.head; i < this.tail; i++) {
                items[i - head] = items[i];
            }
            tail = tail - head;
            head = 0;
            items[tail] = item;
            tail++;
            return true;
        }

        public String dequeue() {
            // 如果head == tail 表示队列为空
            if (head == tail) {
                return null;
            }
            String ret = items[head];
            head++;
            return ret;
        }
    }

    /**
     * 循环队列：
     * 队满：head=tail ; (tail+1)%n = head
     */
    public class CircularQueue {

        private String[] items;
        private int n;

        private int head = 0;
        private int tail = 0;

        public CircularQueue(int capacity) {
            this.items = new String[capacity];
            this.n = capacity;
        }

        public boolean enqueue(String item) {
            // 如果tail == n 表示队列已经满了
            if ((tail + 1) % n == head) {
                return false;
            }
            items[tail] = item;
            tail = (tail + 1) % n;
            return true;
        }

        public String dequeue() {
            // 如果head == tail 表示队列为空
            if (head == tail) {
                return null;
            }
            String ret = items[head];
            head = (head + 1) % n;
            return ret;
        }
    }

    /**
     * 阻塞队列
     * 队列为空，队头取数据阻塞
     * 队列为满，队尾插入数据阻塞
     */
}
